package cxydmmszl.chapter05.t085.hard;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * <li style="color: red;">Prob</li>
 * 完美洗牌问题（2）
 * <li style="color: green;">Desc</li>
 * 给定一个数组arr，请将数组调整为依次相邻的数字，总是先<=、再>=的关系，并交替下去。
 * 比如数组中有五个数字，调整成[a,b,c,d,e]，使之满足a<=b>=c<=d>=e。
 * <li style="color: green;">Input</li>
 * 输入包含两行，第一行一个整数 n（1≤n≤10^5），代表数组的长度，
 * 接下来一行 n 个整数，代表数组 arr（1≤arr[i]≤10^9）。
 * <li style="color: green;">Output</li>
 * 输出一行，代表调整后的数组。
 * <li style="color: blue;">Link</li> CD120
 *
 * @author habitplus
 * @since 2021-09-09 11:23
 */
public class Main {
    private static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return 0;
    }

    public static void main(String[] args) {
        int n = nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        wiggleSort(arr);

        StringBuilder sb = new StringBuilder();
        for (int e : arr) {
            sb.append(e).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static void wiggleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 排序
        Arrays.sort(arr);
        adjustArr(arr);

//        int n = arr.length;
//        int t;
//        if ((n & 1) == 0) {
//            shuffle(arr, 0, n - 1);
//            // 每两个之间进行交换
//            for (int i = 0; i < n; i += 2) {
//                t = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = t;
//            }
//        } else {
//            shuffle(arr, 1, n - 1);
//        }
    }

    private static void adjustArr(int[] arr) {
        if (arr == null || arr.length < 3) return;

        int n = arr.length;
        int[] aux = new int[n / 2];
        int i, j;

        for (i = (n + 1) / 2, j = 0; i < n; j++, i++) aux[j] = arr[i];

        i = (n - 1) / 2;
        j = (n & 1) == 0 ? n - 2 : n - 1;
        while (i > 0) {
            arr[j] = arr[i];
            i--;
            j -= 2;
        }

        for (i = 0; i < aux.length; i++) arr[2 * i + 1] = aux[i];
    }

    /**
     * 在 arr[l...r] 上做完美洗牌调整， n 须为偶数
     */
    public static void shuffle(int[] arr, int l, int r) {
        // 切成一块一块的解决，每一块的长度满足 (3^k)-1
        while (r - l + 1 > 0) {
            int len = r - l + 1;


            // 计算 <=len 且距离 len 最近的，满足 (3^k)-1 的数
            // 也就是找到最大的 k，满足 3^k <= len + 1
            int base = 3, k = 1;
            while (base <= (len + 1) / 3) {
                base *= 3;
                k++;
            }

            // 当前要解决长度为 base - 1 的块，一半就是再除以 2
            int half = (base - 1) / 2;

            // [l...r] 的中点位置
            int mid = (l + r) / 2;

            // 要旋转的左部分为 arr[l+half, mid]，右部分为 arr[mid+1, mid+half]
            // 注意，这里 arr 下标是从 0 开始的
            rotate(arr, l + half, mid, mid + half);

            // 旋转完成后，从 l 开始算起，长度为 base-1 的部分进行下标连续推
            cycles(arr, l, base - 1, k);

            l = l + base - 1;
        }
    }

    // 从 start 位置开始，往右 len 的长度这一段做下标连续推
    // 出发位置依次为 1,3,9...
    private static void cycles(int[] arr, int start, int len, int k) {
        int preVal, cur, tmp;
        // 找到每一个出发位置 trigger，一共 k 个
        // 每一个 trigger 都进行下标连续推
        // 出发位置是从 1 开始算，而数组下标是从 0 开始
        for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
            preVal = arr[trigger + start - 1];
            cur = modifyIndex(trigger, len);
            while (cur != trigger) {
                tmp = arr[cur + start - 1];
                arr[cur + start - 1] = preVal;
                preVal = tmp;
                cur = modifyIndex(cur, len);
            }

            arr[cur + start - 1] = preVal;
        }
    }

    // [l,m] 为左部分，[m+1,r] 为右部分，左右两部分互换
    private static void rotate(int[] arr, int l, int m, int r) {
        reverse(arr, l, m);
        reverse(arr, m + 1, r);
        reverse(arr, l, r);
    }

    // 翻转 arr[l,r]
    private static void reverse(int[] arr, int l, int r) {
        int t;
        while (l < r) {
            t = arr[l];
            arr[l++] = arr[r];
            arr[r--] = t;
        }
    }

    // 数组的长度为 len，调整前的位置是 i，返回调整之后的位置
    // 下标得从 1 开始
    public static int modifyIndex(int i, int len) {
        return (2 * i) % (len + 1);
    }
}
